public class Solution {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode oddEvenList(ListNode head) {
        if (head == null) return head;

        ListNode evenHead = head.next;   // 记录偶链表头
        ListNode odd = head;
        ListNode even = evenHead;

        /* 每次把奇节点指向“下一个奇节点”，偶节点指向“下一个偶节点” */
        while (even != null && even.next != null) {
            odd.next = even.next;   // 奇链表的下一个
            odd = odd.next;         // 奇指针后移
            even.next = odd.next;   // 偶链表的下一个
            even = even.next;       // 偶指针后移
        }
        odd.next = evenHead;        // 把偶链表接到奇链表末尾
        return head;
    }

    /* 根据 int[] 构造链表，返回头节点 */
    private static ListNode buildList(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int num : nums) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }
        return dummy.next;
    }

    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[][] testCases = {
                {1, 2, 3, 4, 5},
                {2, 1, 3, 5, 6, 4, 7},
                {},
                {1},
                {1, 2}
        };

        for (int[] arr : testCases) {
            ListNode head = buildList(arr);
            System.out.print("原始链表: ");
            printList(head);
            ListNode newHead = solution.oddEvenList(head);
            System.out.print("重排后:   ");
            printList(newHead);
            System.out.println("----------------");
        }
    }
}